import java.util.*;

/**
 * 开发了一个工具类来对order进行过滤
 * 时间复杂度  log(n) + N(用户订单数量)
 * 因为UserContext.getCurrentTenantId()这个方法可以得到的是所有的在线的人的tenantId
 * 我就吧所有的在线人的tenantId对应的订单全部找了
 * 如果要过滤单个人的也支持的，getOrdersByTenantId 这个方法实现了根据tenantId来获取到对应的订单
 * ---
 * 如果数据源order不能按tenantId来进行排序的话，那么也可以使用排序算法来先排序在过滤
 * 比如shell排序 那么时间复杂度就来 log(n^1.3 ~ n^1.5) + log(n) + N(用户订单数量) 在多次过滤下会优于list的O(N)遍历的
 * 但是如果是单次过滤，那还是list一次遍历快些
 */
public class DataFilterUtil {

    public static void main(String[] args) throws Exception {
        DataFilterUtil dataFilterUtil = new DataFilterUtil();
        int times = 40;
        for (int i = 0; i < times; i++) {

            List<Order> l = new ArrayList<>();
            Random r = new Random();
            for (int j = 0; j < times; j++) {
                if (r.nextBoolean()) {
                    l.add(new Order(j));
                    l.add(new Order(j));
                    l.add(new Order(j));
                }
                l.add(new Order(j));
            }
            System.out.println(l);
            for (int i1 = 0; i1 < times; i1++) {
                List<Order> ordersByTenantId = dataFilterUtil.getOrdersByTenantId(l, i1);
                System.out.println( ordersByTenantId+ " size = " + ordersByTenantId.size());
                if(ordersByTenantId.size() != 1 && ordersByTenantId.size() != 4){
                    throw new Exception();
                }
            }

            System.out.println("所有在线的id 对饮的订单");
            System.out.println(dataFilterUtil.getCurrentTenantIdOrders(l));
        }

    }

    UserContext userContext = new UserContext();

    //默认这个方法返回的是所有的订单
    List<Order> getOrders() {
        return null;
    }

    /**
     * @param orders 订单信息
     * @return map返回了所有的在线id 和他对应的订单
     */
    public Map<Integer, List<Order>> getCurrentTenantIdOrders(List<Order> orders) {
        //获取到在线用户id
        List<Integer> currentTenantId = userContext.getCurrentTenantId();

        Map<Integer, List<Order>> currentTenantIdOrders = new HashMap<Integer, List<Order>>();

        for (Integer id : currentTenantId) {
            currentTenantIdOrders.put(id, getOrdersByTenantId(orders, id));
        }

        return currentTenantIdOrders;
    }

    /**
     * 在sql查询的时候将order的tenantId按升序排序
     * 那么就可以使用二分查找来实现log(n) 级别的查找效率
     * 最后获取到对应订单的时间复杂度就来到了 log(n) + N(用户订单数量)
     *
     * @param orders   订单
     * @param tenantId 过滤的用户id
     */
    public List<Order> getOrdersByTenantId(List<Order> orders, Integer tenantId) {
        //查找到订单的位置
        Integer index = findTenantId(orders, tenantId);

        if (index == null) {
            System.out.println("该用户没有订单");
            return null;
        }

        List<Order> filterOrders = new ArrayList<>();

        //从index起点 向俩头开始遍历
        // 向左边
        for (int i = index; i >= 0; i--) {
            if (!orders.get(i).tenantId.equals(tenantId)) {
                break;
            }
            filterOrders.add(new Order(orders.get(i)));
        }

        //向右边
        for (int i = index + 1; i < orders.size(); i++) {
            if (!orders.get(i).tenantId.equals(tenantId)) {
                break;
            }
            filterOrders.add(new Order(orders.get(i)));
        }

        return filterOrders;
    }

    //这里找到对应的id 在orders中的下标
    Integer findTenantId(List<Order> orders, Integer tenantId) {
        if (orders == null || tenantId == null) {
            return null;
        }

        int l = 0, r = orders.size();

        while (l < r) {
            int mid = l + (r - l) / 2;
            if (orders.get(mid).tenantId < tenantId) {
                l = mid + 1;
            } else if (orders.get(mid).tenantId.equals(tenantId)) {
                return mid;
            } else {
                r = mid;
            }
        }
        return null;
    }
}
